/*
* File: 		queue.c
* Author: 		Akira
* Date: 		2023-11-15
* Description:  队列的链式存储实现
* Version: 		1.0.0
* Modify: 		None.
*/

#include "queue.h"

//初始化队列
void InitQueue(LinkQueue* q)
{
#if QUEUE_WITH_HEAD_NODE
	//初始化front,rear都指向头节点
	q->front = q->rear = (LinkNode*)malloc(sizeof(LinkNode)); 	//建立头节点
	q->front->next = NULL;
#else
	//初始化front,rear都指向NULL
	q->front = NULL;
	q->rear = NULL;
#endif

	q->length = 0;
}

//判断队列是否为空
bool IsEmpty(LinkQueue* q)
{
#if QUEUE_WITH_HEAD_NODE
	if(q->front == q->rear) return true;
	else return false;
#else
	if(q->front == NULL) return true;
	else return false;
#endif
}

//入队
bool EnQueue(LinkQueue* q, ElemType x)
{
	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = NULL;

#if QUEUE_WITH_HEAD_NODE
	q->rear->next = s;							//新节点插入到rear节点之后
	q->rear = s;								//修改rear指针
#else
	if(q->front == NULL)						//在空队列中插入第一个元素
	{
		q->front = s;
		q->rear = s;
	}
	else
	{
		q->rear->next = s;						//新节点插入到rear节点之后
		q->rear = s;							//修改rear指针
	}
#endif

	q->length++;
	return true;
}

//出队
bool DeQueue(LinkQueue* q, ElemType* x)
{
#if QUEUE_WITH_HEAD_NODE
	if(q->front == q->rear) return false;		//队空

	LinkNode* p = q->front->next;
	*x = p->data;								//用x返回队头元素

	q->front->next = p->next;					//修改头节点的next指针
	if(q->rear == p)							//若是最后一个节点出队
		q->rear = q->front;
#else
	if(q->front == NULL) return false;			//队空

	LinkNode* p = q->front;						//p指向此次出队的节点
	*x = p->data;								//用x返回队头指针

	q->front = p->next;							//修改front指针
	if(q->rear == p)							//此次是最后一个节点出队
	{
		q->front = NULL;						//front指向NULL
		q->rear = NULL;							//rear指向NULL
	}
#endif
	free(p);									//释放节点空间

	q->length--;
	return true;
}

//求队列长度
int LengthQueue(LinkQueue* q)
{
#if QUEUE_WITH_HEAD_NODE
	return q->length;
#else
	int count = 0;
	LinkNode* p = q->front;
	while(p != NULL)
	{
		++count;
		p = p->next;
	}
	return count;
#endif
}

//读取队头元素
bool GetLead(LinkQueue *q, ElemType *x)
{
#if QUEUE_WITH_HEAD_NODE
	if(q->front == q->rear) return false;
	*x = q->front->next->data;
#else
	if(q->front == NULL) return false;
	*x = q->front->data;
#endif
	return true;
}
